Binary Search Tree Iterator || Binary Tree Zigzag Level Order Traversal

发表于

Binary Search Tree Iterator

Question

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Analysis

  • 利用栈保存根节点的所有直接左节点
  • 判断是否存在next节点可以直接通过栈是否为空来判断
  • next函数在pop当前节点后push该节点的所有直接左节点

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class BSTIterator {
    
    private Stack<TreeNode> stack=new Stack<TreeNode>();
    public BSTIterator(TreeNode root) {
        pushAll(root);
    }
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    /** @return the next smallest number */
    public int next() {
        TreeNode node=stack.pop();
        pushAll(node.right);
        return node.val;
    }
    
    public void pushAll(TreeNode node){
        for(;node!=null;node=node.left)
            stack.push(node);
    }
}
/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */

Binary Tree Zigzag Level Order Traversal

Question

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its zigzag level order traversal as:

1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

Analysis

  • 利用linkedlist来保存每层的节点，偶数层的节点从前向后插入，奇数层节点每次插入在头节点处
  • 利用两个变量parent，child来记录每层节点个数，从而确定从queue中poll的次数，parent保存当前层的节点个数，child保存下一层的节点个数
  • 在一开始的时候判断root是否为空

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();
        if(root==null)
            return res;
        int level=0;    //Judge odd or even by mod
        int child=0;    //Number of child node
        int parent=1;   //Number of nodes in current level
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        List<Integer> tmp=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            
            if(level%2==0)
                tmp.add(node.val);
            else
                tmp.add(0,node.val);
            
            if(node.left!=null){
                queue.add(node.left);
                child++;
            }
            if(node.right!=null){
                queue.add(node.right);
                child++;
            }
            parent--;
            
            if(parent==0){
                res.add(tmp);
                level++;
                tmp=new LinkedList<>();
                parent=child;
                child=0;
            }
        }
        return res;
    }
}